import java.util.*;

/**
 * Created by L.jp
 * Description:给定一个 N 叉树，返回其节点值的层序遍历。（即从左到右，逐层遍历）。
 *
 * 树的序列化输入是用层序遍历，每组子节点都由 null 值分隔（参见示例）。
 *
 * 输入：root = [1,null,3,2,4,null,5,6]
 * 输出：[[1],[3,2,4],[5,6]]
 *
 * User: 86189
 * Date: 2021-11-28
 * Time: 23:21
 */
class Node {
    public int val;
    public List<Node> children;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, List<Node> _children) {
        val = _val;
        children = _children;
    }
}
public class NaryTree {
    public List<List<Integer>> levelOrder(Node root){
        Queue<Node> queue=new LinkedList<>();//层序遍历就是队列的先进先出原则，用队列存储每个节点
        List<List<Integer>> list=new ArrayList<>();//存储最终层序遍历得到的每层节点的值
        if(root==null){
            return list;
        }
        queue.offer(root);//先将根节点加入队列
        while(!queue.isEmpty()) {
            int qSize=queue.size();
            List<Integer> tmpList=new ArrayList<>();//每次将临时列表的值加入到总的列表之后都要重新创建一个临时列表存储当前层节点的h值
            while(qSize!=0){
                Node curNode=queue.peek();//得到队头节点，以便于遍历他的孩子节点
                queue.poll();//弹出节点
                qSize--;//长度减1
                tmpList.add(curNode.val);//将弹出的节点的值加入到临时列表
                for(Node child:curNode.children){//遍历弹出的节点的孩子节点
                    if(child!=null) {
                        queue.offer(child);//将孩子节点加入到队列
                    }
                }
            }
            //当队列长度为0时说明所有的节点度遍历完了，将临时列表加入到总的列表中
            if(tmpList.size()!=0) {
                list.add(tmpList);
            }
        }
        return list;
    }
}
